二叉树的搜索

function Node (value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

const a = new Node('a');
const b = new Node('b');
const c = new Node('c');
const d = new Node('d');
const e = new Node('e');
const f = new Node('f');
const g = new Node('g');

a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.left = f;
c.right = g;

深度优先搜索

function deepSearch (root, target) {
    if (root == null) return false;
    if (root.value == target) return true;
    const left = deepSearch(root.left, target);
    const right = deepSearch(root.right, target);
    return left || right;
}
console.log(deepSearch(a, 'e')); //--> true

对于二叉树来说：深度优先搜索与前序遍历的顺序是一致的。

广度优先搜索

function wideSearch (rootList, target) {
    if (rootList == null || rootList.length == 0) return false;
    const childList = [];  // 存放子节点
    for (let i = 0; i < rootList.length; i ++) {
        if (rootList[i] != null && rootList[i] == target) {
            return true;
        } else {
            childList.push(rootList[i].left);
            childList.push(rootList[i].right);
        }
    }
    return wideSearch(childList, target);
}
console.log(wideSearch([a], e));  //--> true